{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Forbidden-CNot Expansions\n",
    "\n",
    "Most chips are not fully connected (not all pairs of qubits are\n",
    "physically connected). Furthermore, even if two qubits are connected,\n",
    "one of them may be forbidden as a target of a CNOT between\n",
    "the 2 qubits. The Qubiter file `ForbiddenCNotExpander.py`\n",
    "contains an \"expander\" class of the same name that is \n",
    "designed to circumvent this chip limitation.\n",
    "\n",
    "The class reads an English file and outputs a new English file and\n",
    "corresponding Picture file. The new English file differs from the initial\n",
    "English file in that each forbbiden CNOT is expanded into a sequence of Hadamards\n",
    "and allowed, elementary CNOTs.\n",
    "\n",
    "This notebook shows 2 examples of the usage of this class.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "/home/rrtucci/PycharmProjects/qubiter/qubiter/jupyter_notebooks\n",
      "/home/rrtucci/PycharmProjects/qubiter\n"
     ]
    }
   ],
   "source": [
    "# Make the qubiter directory the cwd (current working directory) and \n",
    "# add its path to the path environment variable\n",
    "import os\n",
    "import sys\n",
    "print(os.getcwd())\n",
    "os.chdir('../../')\n",
    "print(os.getcwd())\n",
    "sys.path.insert(0,os.getcwd())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next we import the class `ForbiddenCNotExpander` and print its very informative docstring so you can read it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "loaded OneQubitGate, WITHOUT autograd.numpy\n"
     ]
    }
   ],
   "source": [
    "from qubiter.device_specific.ForbiddenCNotExpander import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# this tells notebook to send pager output to cell below instead of pager\n",
    "from __future__ import print_function\n",
    "\n",
    "def page_printer(data, start=0, screen_lines=0, pager_cmd=None):\n",
    "    if isinstance(data, dict):\n",
    "        data = data['text/plain']\n",
    "    print(data)\n",
    "\n",
    "import IPython.core.page\n",
    "IPython.core.page.page = page_printer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[0;31mInit signature:\u001b[0m \u001b[0mForbiddenCNotExpander\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mfile_prefix\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mnum_qbits\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mc_to_tars\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mDocstring:\u001b[0m     \n",
      "Most chips are not fully connected (not all pairs of qubits are\n",
      "physically connected). Furthermore, even if two qubits are connected,\n",
      "one of them may be disallowed, forbidden, as a target of a CNOT between\n",
      "the 2 qubits. This class is designed to circumvent this chip limitation.\n",
      "\n",
      "This class is a child of the class EchoingSEO_reader. It is one of\n",
      "several expander classes that replace certain single gates by expansions\n",
      "(sequences) of other gates.\n",
      "\n",
      "The class reads an English file and outputs a new English file and\n",
      "corresponding Picture file. The new English file echoes every line of\n",
      "the original English file except for those lines which are SIGX with one\n",
      "or more controls.\n",
      "\n",
      "If this class reads a line which is a SIGX with > 1 controls, it outputs\n",
      "an error message. In such a case, you should use the class CGateExpander\n",
      "first to expand such gates into single qubit rotations and simple CNOTs\n",
      "with a single control.\n",
      "\n",
      "If this class reads a line which is a SIGX with a single control,\n",
      "it echoes it if such a CNOT is allowed according to the input list\n",
      "'c_to_tars'. Otherwise, it replaces the disallowed (a.k.a., forbidden,\n",
      "unphysical, between disconnected qubits) CNOT by a sequence of Hadamards\n",
      "and allowed, elementary CNOTs.\n",
      "\n",
      "Next we explain the expansion used by this class to replace forbidden\n",
      "CNOTs.\n",
      "\n",
      "Let us denote a CNot with control a and target b by C(a->b)=C(a, b)\n",
      "\n",
      "Note that if C(a, b) is forbidden but C(b, a) is allowed, we can express\n",
      "the forbidden one in terms of the allowed one and four Hadamard matrices\n",
      "using the identity (X is the target SIGX and @ is the True control)\n",
      "\n",
      "X---@\n",
      "equals\n",
      "H   H\n",
      "@---X\n",
      "H   H\n",
      "\n",
      "Note that\n",
      "\n",
      "X---+---@\n",
      "equals\n",
      "X---@   |\n",
      "|   X---@\n",
      "X---@   |\n",
      "|   X---@\n",
      "equals\n",
      "|   X---@\n",
      "X---@   |\n",
      "|   X---@\n",
      "X---@   |\n",
      "\n",
      "One can generalize the previous identity as follows:\n",
      "\n",
      "X---+---+---@\n",
      "equals\n",
      "X---+---@   |\n",
      "|   |   X---@\n",
      "X---+---@   |\n",
      "|   |   X---@\n",
      "equals\n",
      "|   X---@   |\n",
      "X---@   |   |\n",
      "|   X---@   |\n",
      "X---@   |   |\n",
      "|   |   X---@\n",
      "X---@   |   |\n",
      "|   X---@   |\n",
      "X---@   |   |\n",
      "|   X---@   |\n",
      "|   |   X---@\n",
      "equals (cancel two internal CNots)\n",
      "|   X---@   |\n",
      "X---@   |   |\n",
      "|   X---@   |\n",
      "|   |   X---@\n",
      "|   X---@   |\n",
      "X---@   |   |\n",
      "|   X---@   |\n",
      "|   |   X---@\n",
      "\n",
      "One can generalize the previous identity as follows:\n",
      "\n",
      "X---+---+---+---@\n",
      "equals\n",
      "|   |   X---@   |\n",
      "|   X---@   |   |\n",
      "X---@   |   |   |\n",
      "|   X---@   |   |\n",
      "|   |   X---@   |\n",
      "|   |   |   X---@\n",
      "|   |   X---@   |\n",
      "|   X---@   |   |\n",
      "X---@   |   |   |\n",
      "|   X---@   |   |\n",
      "|   |   X---@   |\n",
      "|   |   |   X---@\n",
      "\n",
      "In general, let's define a composite V gate (called V because it looks\n",
      "like a V lying on its side) as follows:\n",
      "\n",
      "V(0->4) =\n",
      "|   |   |   X---@\n",
      "|   |   X---@   |\n",
      "|   X---@   |   |\n",
      "X---@   |   |   |\n",
      "|   X---@   |   |\n",
      "|   |   X---@   |\n",
      "|   |   |   X---@\n",
      "\n",
      "Above, 0, 1, 2, 3, 4 can be replaced by any other distinct qubits. Also,\n",
      "on can define an analogous V for any number >= 2 of qubits.\n",
      "\n",
      "If\n",
      "C(0->4)=\n",
      "X---+---+---+---@\n",
      "then we proved above that\n",
      "\n",
      "C(0->4)= V(0->4)V(1->4)\n",
      "\n",
      "In fact, we also proved\n",
      "\n",
      "C(0->j)= V(0->j)V(1->j) for j = 2, 3, 4, ...\n",
      "\n",
      "We like to refer to the last equation as the vv expansion of C(0->j). In\n",
      "this class, we expand a forbidden CNot C(trol->targ) using the last\n",
      "equation with the qubit positions 0, 1, 2, ..., j in the last equation\n",
      "mapped in a 1-1 onto fashion to qubit positions along a path of qubits\n",
      "connecting the two qubits trol and targ. The path is found by calling\n",
      "the python networkx function that yields the shortest path between two\n",
      "nodes of an undirected graph G. We let G be the undirected graph that\n",
      "has as edges all pairs of qubits that are coupled according to the input\n",
      "`c_to_tars`.\n",
      "\n",
      "Attributes\n",
      "----------\n",
      "c_to_tars : dict[int, list[int]]\n",
      "    a dictionary mapping j in range(num_qbits) to a list, possibly empty,\n",
      "    of the physically allowed targets of qubit j, when j is the control\n",
      "    of a CNOT.\n",
      "graph : networkx.Graph\n",
      "    A networkx undirected graph derived from `c_to_tars` by taking all\n",
      "    items in get_dir_edges_from_c_to_tars(c_to_tars) as edges.\n",
      "\u001b[0;31mInit docstring:\u001b[0m\n",
      "Constructor\n",
      "\n",
      "Parameters\n",
      "----------\n",
      "file_prefix : str\n",
      "num_qbits : int\n",
      "c_to_tars : dict[int, list[int]]\n",
      "\n",
      "Returns\n",
      "-------\n",
      "\u001b[0;31mFile:\u001b[0m           ~/PycharmProjects/qubiter/qubiter/device_specific/ForbiddenCNotExpander.py\n",
      "\u001b[0;31mType:\u001b[0m           type\n",
      "\u001b[0;31mSubclasses:\u001b[0m     \n",
      "\n"
     ]
    }
   ],
   "source": [
    "ForbiddenCNotExpander?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "import qubiter.device_specific.chip_couplings_ibm as ibm\n",
    "num_qbits = 5\n",
    "c_to_tars = ibm.ibmqx2_c_to_tars\n",
    "file_prefix = \"forbidden_cnots_ibm\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is the input English file for this example:\n",
    "\n",
    "<a href='../io_folder/forbidden_cnots_ibm_5_eng.txt'>../io_folder/forbidden_cnots_ibm_5_eng.txt</a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next we create an object of our expander class."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<qubiter.device_specific.ForbiddenCNotExpander.ForbiddenCNotExpander at 0x7f4f829c1cd0>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ForbiddenCNotExpander(file_prefix, num_qbits, c_to_tars)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following 2 files were generated by the constructor just called:\n",
    "\n",
    "* <a href='../io_folder/forbidden_cnots_ibm_X1_5_eng.txt'>../io_folder/forbidden_cnots_ibm_X1_5_eng.txt</a>\n",
    "* <a href='../io_folder/forbidden_cnots_ibm_X1_5_ZLpic.txt'>../io_folder/forbidden_cnots_ibm_X1_5_ZLpic.txt</a>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "num_qbits = 4\n",
    "c_to_tars = {0: [1], 1: [2], 2: [3], 3: []}\n",
    "file_prefix = \"forbidden_cnots1\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is the input English file for this example:\n",
    "\n",
    "<a href='../io_folder/forbidden_cnots1_4_eng.txt'>../io_folder/forbidden_cnots1_4_eng.txt</a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next we create an object of our expander class."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<qubiter.device_specific.ForbiddenCNotExpander.ForbiddenCNotExpander at 0x7f4f829bc890>"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ForbiddenCNotExpander(file_prefix, num_qbits, c_to_tars)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following 2 files were generated by the constructor just called:\n",
    "\n",
    "* <a href='../io_folder/forbidden_cnots1_X1_4_eng.txt'>../io_folder/forbidden_cnots1_X1_4_eng.txt</a>\n",
    "* <a href='../io_folder/forbidden_cnots1_X1_4_ZLpic.txt'>../io_folder/forbidden_cnots1_X1_4_ZLpic.txt</a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {
    "height": "66px",
    "width": "252px"
   },
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": "block",
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
